package tree;

import queue.LinkedQueue;
import stack.LinkedStack;
import stack.Stack;

public class BinaryTree<T> implements IBinaryTree<T> {
    public BinaryNode<T> root;                  //根结点，二叉链表结点结构

    public BinaryTree() {
        this.root = null;
    }

    public static void main(String[] args) {

        //                   A
        //                /     \
        //               B       C
        //             /   \    /  \
        //            D     E   F   G
        //                 /     \
        //                H       I
        //                       /
        //                      J

        // 初始化树
        BinaryTree<Character> btree = new BinaryTree<Character>();
        BinaryNode<Character> nodeA = btree.insert('A');

        // 左子树
        BinaryNode<Character> nodeB = btree.insert(nodeA, 'B', true);
        BinaryNode<Character> nodeD = btree.insert(nodeB, 'D', true);
        BinaryNode<Character> nodeE = btree.insert(nodeB, 'E', false);
        BinaryNode<Character> nodeH = btree.insert(nodeE, 'H', true);

        // 右子树
        BinaryNode<Character> nodeC = btree.insert(nodeA, 'C', false);
        BinaryNode<Character> nodeF = btree.insert(nodeC, 'F', true);
        BinaryNode<Character> nodeG = btree.insert(nodeC, 'G', false);
        BinaryNode<Character> nodeI = btree.insert(nodeF, 'I', false);
        BinaryNode<Character> nodeJ = btree.insert(nodeI, 'J', true);


        System.out.println(btree);
        System.out.println(btree.size());
        System.out.println(btree.height());

        // 遍历
        System.out.println("preOrder, inOrder, postOrder:");
        btree.preOrder();
        btree.inOrder();
        btree.postOrder();

        System.out.println("preOrderTraverse, inOrderTraverse, levelOrder:");
        btree.preOrderTraverse();
        btree.inOrderTraverse();
        btree.levelOrder();

    }

    @Override
    public boolean isEmpty() {
        return this.root == null ;
    }

    //插入x作为根结点，原根结点作为x的左孩子；返回插入结点
    @Override
    public BinaryNode<T> insert(T x) {
        if (x==null)
            return null;
        BinaryNode<T> newNode = new BinaryNode<T>(x,this.root,null);
        this.root=newNode;
        return  newNode;
    }

    //插入x为parent结点的左/右孩子，leftChild指定孩子，取值为true（左）、false（右）；
    //parent的原左/右孩子成为x结点的左/右孩子；返回插入结点。
    @Override
    public BinaryNode<T> insert(BinaryNode<T> parent, T x, boolean leftChild) {
        if(x == null)
            return null;
        BinaryNode<T> newNode;
        if(leftChild){
            newNode = new BinaryNode<T>(x,parent.left,null);
            parent.left=newNode;
        }
        else {
            newNode=new BinaryNode<T>(x,null,parent.right);
            parent.right=newNode;
        }
        return newNode;
    }

    @Override
    public String toString() {
        return toString(this.root);
    }

    private String toString(BinaryNode<T> p) {
        if(p==null){
            return "^";
        }
        if(p.left == null && p.right == null){
            return p.data.toString();
        }
        else {
            return p.data.toString()+"(" + toString(p.left) + "," + toString(p.right) + ")";
        }
    }

    @Override
    public int size() {
        return size(root);
    }

    int n = 0;
    private int size(BinaryNode<T> p) {
//        if (p!=null)
//        {
//            n++;
//            size(p.left);
//            size(p.right);
//        }
//        return n;
        if (p == null) {
            return 0;
        }
        return 1 + size(p.left) + size(p.right);
    }

    @Override
    public int height() {
        return height(root);
    }

    private int height(BinaryNode<T> p) {
        if (p == null) {
            return 0;
        }
        int lh = height(p.left);
        int rh = height(p.right);
        return (lh >= rh) ? lh + 1 : rh + 1;
    }

    @Override
    public void remove(BinaryNode<T> parent, boolean leftChild) {
        if (parent != null) {
            if (leftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
    }

    @Override
    public void clear() {
        this.root = null;
    }


    @Override
    public void preOrder() {
        preOrder(this.root);
        System.out.println();
    }

    private void preOrder(BinaryNode<T> p) {
        if(p!=null)
        {
            System.out.print(p.data.toString()+" ");
            preOrder(p.left);
            preOrder(p.right);
        }

    }

    @Override
    public void inOrder() {
        inOrder(this.root);
        System.out.println();
    }
    private void inOrder(BinaryNode<T> p) {
        if(p!=null)
        {
            inOrder(p.left);
            System.out.print(p.data.toString()+" ");
            inOrder(p.right);
        }
    }

    @Override
    public void postOrder() {
        postOrder(this.root);
        System.out.println();
    }
    private void postOrder(BinaryNode<T> p) {           //后根次序遍历以p结点为根的子树，递归方法
        if(p!=null)
        {
            postOrder(p.left);
            postOrder(p.right);
            System.out.print(p.data.toString()+" ");   // 后访问当前结点元素
        }

    }

    @Override
    public void preOrderTraverse() {
        Stack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while(p!=null || !stack.isEmpty())
        {
            if(p!=null)
            {
                System.out.print(p.data+" ");
                stack.push(p);
                p=p.left;
            }
            else
            {
//                System.out.print("^ ");
                p=stack.pop();
                p=p.right;
            }
        }
        System.out.println();
    }

    @Override
    public void inOrderTraverse() {
        Stack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while(p!=null || !stack.isEmpty())
        {
            if(p!=null)
            {
                stack.push(p);
                p=p.left;
            }
            else
            {
                p=stack.pop();
                System.out.print(p.data+" ");
                p=p.right;
            }
        }
        System.out.println();
    }

    @Override
    public void levelOrder() {
        if(this.root==null)
            return;
        //创建空队列，其中队列的元素类型是二叉树结点 BinaryNode<T>
        LinkedQueue<BinaryNode<T>> que = new LinkedQueue<BinaryNode<T>>();
        que.add(this.root);
        while(!que.isEmpty())
        {
            BinaryNode<T> p =que.poll();
            System.out.print(p.data+" ");
            if(p.left!=null)
                que.add(p.left);
            if(p.right!=null)
                que.add(p.right);
        }
        System.out.println();
    }
}